package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/9/7 11:30
 * @Description:一棵树是否是另一棵树的子树
 * https://leetcode-cn.com/problems/subtree-of-another-tree/
 */
public class Num572_IsSubTree {
    /**
     * 判断一棵树是否是另一棵树的子树问题本质上就是在判断一棵树和另一棵树中的某个子树是否相等。
     * 进一步转化为判断s是否包含t => s和t是否相等||s.left是否包含t || s.right是否包含t
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null)
            return true;
        if (root == null || subRoot == null)
            return false;
        // s与t是否相同 || s的左树是否与t相同 || s的右树是否与t相同
        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) ||
                isSubtree(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 先处理根节点的情况
        // 1.两树都为空，一定相同
        // 2.两树其中有一颗为空，一定不相同
        // 3.两树根节点都不为空，判断根节点的值，再递归判断左树和右树的情况
        if (p == null && q == null)
            return true;
        // 走到这一步表示p和q一定一个不为空
        if (p == null || q == null)
            return false;
        // 此时两树都不为空
        if (p.val != q.val)
            return false;
        // 继续查看左树和右树是否完全相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}
